public class SudokuSolver {
    private int[][] board;

    public SudokuSolver(int[][] board) {
        this.board = board;
    }

    public void solve() {
        if (solveHelper(0, 0)) {
            printBoard();
        } else {
            System.out.println("No solution found");
        }
    }

    private boolean solveHelper(int row, int col) {
        if (col == 9) {
            col = 0;
            row++;
            if (row == 9) {
                return true;
            }
        }
        if (board[row][col] != 0) {
            return solveHelper(row, col + 1);
        }
        for (int num = 1; num <= 9; num++) {
            if (isValid(row, col, num)) {
                board[row][col] = num;
                if (solveHelper(row, col + 1)) {
                    return true;
                }
                board[row][col] = 0;
            }
        }
        return false;
    }

    private boolean isValid(int row, int col, int num) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num || board[i][col] == num) {
                return false;
            }
            int boxRow = 3 * (row / 3) + i / 3;
            int boxCol = 3 * (col / 3) + i % 3;
            if (board[boxRow][boxCol] == num) {
                return false;
            }
        }
        return true;
    }

    private void printBoard() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] board = {{6, 0, 9, 0, 0, 0, 7, 0, 4},
                         {0, 0, 0, 0, 5, 0, 0, 9, 8},
                         {0, 0, 7, 0, 2, 4, 0, 0, 0},
                         {4, 0, 0, 0, 0, 3, 0, 7, 0},
                         {0, 9, 0, 0, 0, 0, 0, 8, 0},
                         {0, 7, 0, 2, 0, 0, 0, 0, 3},
                         {0, 0, 0, 6, 1, 0, 3, 0, 0},
                         {3, 1, 0, 0, 7, 0, 0, 0, 0},
                         {7, 0, 6, 0, 0, 0, 4, 0, 5}};
        SudokuSolver solver = new SudokuSolver(board);
        solver.solve();
    }
}